package com.MSB2.sort2;


import java.util.Comparator;
import java.util.PriorityQueue;

public class HeapSort {

    public static void main(String[] args) {
        int[] arr = {40, 3, 2, 45, 53, 2234, 12, 54, 5234, 32, 2347, 1, 343, 4};
        heapSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
//        PriorityQueue<Integer> heap = new PriorityQueue<>();
    }

    public static void heapSort(int[] arr){
        int heapSize = arr.length;
//        int[] heap = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
//            heap[i] = arr[i];
            heapInsert(arr, i);
        }
        for (int i = arr.length - 1; i >= 0 ; i--) {
            swap(arr, 0, i);
            heapSize --;
            heapify(arr, 0, heapSize);
        }
//        System.arraycopy(heap,0, arr, 0, arr.length);
    }

    private static void heapInsert(int[] arr, int index){
        int parent = (index - 1) / 2;
        while (arr[index] > arr[parent]){
            swap(arr, index, parent);
            index = parent;
            parent = (index - 1) / 2;
        }
    }

    private static void heapify(int[] arr, int index, int heapSize){
        int left = index * 2 + 1;
        while (left < heapSize){
            int largest = left;
            if (left + 1 < heapSize && arr[left] < arr[left + 1]){
                largest = left + 1;
            }
            if (arr[largest] <= arr[index]){
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }
    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }
}
